package com.ywk.base.javaBase.collection.list;

import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;

/**
 * - ArrayList：基于动态数组实现，支持随机访问（RandomAccess 接口标识着该类支持快速随机访问），线程不安全，扩容：原来的1.5倍
 * - Vector：和 ArrayList 类似，但它是线程安全的（synchronized），扩容：原来的2倍
 * - LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。
 *
 * @Author zbh
 * @Date 2023/3/30
 */
public class ListDemo {

    public static void main(String[] args) {
        /*===================================ArrayList======================================*/
        /**
         * 使用 elementData 存储信息，数组的默认大小：10
         *
         * 扩容：ensureCapacityInternal() 保证容量足够，grow() 进行扩容，新容量的大小为 `oldCapacity + (oldCapacity >> 1)`，
         * 即 oldCapacity+oldCapacity/2。其中 oldCapacity >> 1 需要取整，所以新容量大约是旧容量的 1.5 倍左右。（oldCapacity 为偶数就是 1.5 倍，为奇数就是 1.5 倍-0.5）
         *（注：扩容操作需要调用 `Arrays.copyOf()` 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，
         * 减少扩容操作的次数，删除元素需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)，
         * 所以 ArrayList 删除元素的代价是非常高的。）
         *
         * */
        List<String> list = new ArrayList<>();
        list.add("1");

        //线程不安全解决办法
        //可以使用 `Collections.synchronizedList();` 得到一个线程安全的 ArrayList。
        List<String> synList = Collections.synchronizedList(list);
        /**
         * 也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。
         * 读写分离：操作在一个复制的数组上进行，读操作还是在原始数组中进行，写操作需要加锁，防止并发写入时导致写入数据丢失，写操作结束之后需要把原始数组指向新的复制数组
         *
         * 适用场景：
         * CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。但是 CopyOnWriteArrayList 有其缺陷：
         * - 内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
         * - 数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。
         * 所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。
         *
         * */
        List<String> list2 = new CopyOnWriteArrayList<>();


        /*===================================Vector======================================*/
        Vector<String> vector = new Vector();
        vector.add("1");

        /*===================================LinkedList======================================*/
        /**
         * 使用 Node 存储链表节点信息，每个链表存储了 first 和 last 指针；
         *
         * ArrayList 和 LinkedList 的区别（归结为数组和链表的区别）：
         * - 数组支持随机访问，但插入删除的代价很高，需要移动大量元素；
         * - 链表不支持随机访问，但插入删除只需要改变指针。
        * */
        LinkedList<String> linkedList = new LinkedList<>();

    }
}
